from typing import List


class Solution:
    # 返回最大长度
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        dp = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

    def func(self, nums: List):
        if not nums:
            return nums
        dp = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
            result = []
            max_len = max(dp)
            for k in range(len(nums)):
                if dp[k] == max_len:
                    result.append(nums[k])
                    max_len -= 1
        return dp

    # 返回该最长序列
    def pathOfLIS(self, nums: List[int]) -> List:
        if not nums:
            return nums
        n = len(nums)
        dp = [0] * n
        for i in range(n-2, -1, -1):
            for j in range(n-1, i, -1):
                if nums[i] < nums[j] and dp[i] <= dp[j]:
                    dp[i] += 1
            max_len = max(dp)
            result = []
            for k in range(n):
                if dp[k] == max_len:
                    result.append(nums[k])
                    max_len -= 1
        return result


if __name__ == '__main__':
    x = Solution()
    t = [10,9,2,5,3,7,101,18]
    print(x.pathOfLIS(t))
